Packet-switched data networks include various devices, such as routers, interconnected through multiple types of network connections and topologies, that control the forwarding of data packets. A router may create or maintain a table of the available routes and their conditions, and use this information along with distance and cost algorithms to determine the best route for a given data packet. Typically, a data packet may travel through a number of network points with routers before arriving at its destination.
Routing protocols may be used in data networks to discover other routers and to provide for timely and efficient routing of data packets. Routing may involve maintaining a routing table that contains the information necessary to forward a data packet along the best path toward its destination. Each data packet may contain information about its origin and destination. When a data packet is received, a network device examines the data packet and matches it to the routing table entry providing the best match for its destination. The table then provides the device with instructions for sending the data packet to the next hop on its route across the network.
In order for a routing protocol to work, each network device must have a unique address. Traditional identifiers, such as media access controller (MAC) addresses, serial numbers, etc., may be used as network device addresses because they provide guaranteed uniqueness. However, these traditional identifiers may be long and, therefore, not very user friendly. Moreover, long traditional identifiers may create unnecessary overhead in a data packet. A shorter address could also be used but must be guaranteed to be unique.
In some applications, such as private interconnects between stackable switches, shorter addresses, sometimes automatically selected or assigned, are often used as aliases for addressing in data path forwarding in order to minimize packet overhead. Unfortunately, a routing protocol may not be able to use these shorter addresses directly because they may not be guaranteed to be unique.
Conventional solutions to this problem involve the use of a long, unique address for routing and discovery of devices, followed by the automatic assignment of a shorter address as an alias for the longer address. This approach is one of conflict avoidance—first network devices are discovered based on longer unique addresses, and then automated address assignment is performed to ensure uniqueness of addresses. Unfortunately, this approach may be problematic for several reasons. Manual assignment of addresses may be much preferred over automated assignment. For example, it is likely desirable to assign similar addresses to network devices that are in close proximity. In this way, automatic assignment may not assign a short address in a way that is friendly to a user of the network (i.e., the shorter address may not reflect the physical location of a device in the network or may not reflect user preferences). Additionally, changing the addresses of a network device (which may occur if assignment is automated) can be highly undesirable. For example, in an application of a private interconnect between stackable switches, the short address alias may be used outside of the routing protocol (for instance in configuration or management applications). Automatically re-assigning the address in such applications would have severe negative implications. Finally, if two networks are merged, more than one device may end up with the same short address, which can trigger (multiple) address reassignments, thereby forcing network devices into a temporary inoperable or unstable state until address conflicts are resolved. It may be preferable in some applications to keep the original networks intact, thus providing continuous connectivity on the original network(s), rather than merge them and create a temporarily unstable network. As such, automatic address assignment is undesirable in some applications.
Ensuring the uniqueness of a network device address for routing purposes has been a problem since the existence of routing protocols. Perlman et al. (U.S. Pat. No. 6,898,187) describes advertising devices that detect duplicate network device addresses. The advertising devices then infer whether it is a real duplicate by using a threshold of mismatch of sent and received sequence numbers. If the inference is positive, one of the advertisers selects a different address. This is a strategy of conflict detection and correction which suffers many of the shortcomings discussed earlier.
Chin et al. (K. W. Chin et. al., Routing in MANETs with Address Conflicts; The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services; 2005) describes a routing protocol where duplicate network device addresses are allowed in the context of mobile ad-hoc networks. The Chin et al. routing protocol utilizes an extra identifier appended onto a routing address to make the address unique. However, the resulting unique address is very long and therefore would create a lot of unnecessary overhead within a data packet, and a lot of complexity in the forwarding decision.
Other known address conflict protocols rely on servers. Therefore their applicability to use in routing protocols may be limited in that the servers cannot generally be reached without the connectivity provided by the routing protocol. Furthermore, these assignment protocols may not allow manual address assignments.